/**
 * 
 */
package leetCode;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @author zhong
 *
 */
public class OpentheLock {
	public int openLock(String[] deadends, String target) {
		int[] targets = new int[4];
		for (int i = 0; i < targets.length; i++) {
			targets[i] = target.charAt(i) - '0';
		}

		HashSet<String> deads = new HashSet<>();
		for (String string : deadends) {
			deads.add(string);
		}
		char left = '0' - 1;
		char right = '9' + 1;
		int[][] neib = { { 1, 0, 0, 0 }, { 0, 1, 0, 0 }, { 0, 0, 1, 0 }, { 0, 0, 0, 1 }, { -1, 0, 0, 0 },
				{ 0, -1, 0, 0 }, { 0, 0, -1, 0 }, { 0, 0, 0, -1 } };
		int step = 0;
		HashSet<String> visited = new HashSet<>();
		String start = "0000";
		Queue<String> queue = new LinkedList<>();
		if (!deads.contains(start)) {
			queue.add(start);
			visited.add(start);
		}
		while (!queue.isEmpty()) {
			int size = queue.size();
			for (int c = 0; c < size; c++) {
				String cur = queue.poll();
				if (cur.equals(target)) {
					return step;
				}
				for (int[] is : neib) {// 加入所有可访问的邻居
					StringBuilder sBuilder = new StringBuilder();
					for (int i = 0; i < 4; i++) {
						char ch = (char) (cur.charAt(i) + is[i]);
						if (ch == left) {
							ch = '9';
						} else if (ch == right) {
							ch = '0';
						}
						sBuilder.append(ch);
					}
					String nb = sBuilder.toString();
					if (!deads.contains(nb) && visited.add(nb)) {
						queue.add(nb);
					}
				}
			}
			step++;
		}
		return -1;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		String[] deadends = { "7666", "7677", "8787", "6877", "7788", "6767", "7787", "8667", "7866", "6767", "8886",
				"8686", "8778", "8677", "6688", "6676", "8866", "6787", "7888", "8877", "8788", "7666", "6666", "6776",
				"8686", "8786", "8676", "6887", "8668", "6676", "7777", "6877", "8676", "7768", "6888", "8666", "7876",
				"8776", "8878", "8687", "8676", "6876", "8686", "6886", "8687", "7666", "7776", "6788", "6876", "7866",
				"8666", "8868", "7888", "7767", "8668", "7668", "7666", "7767", "6767", "7866", "8666", "7667", "7766",
				"6786", "7766", "8767", "6676", "7777", "8687", "8768", "7786", "7868", "6867", "6788", "7786", "6778",
				"7667", "8866", "8866", "7787", "6777", "6878", "7877", "6876", "6868", "7886", "6876", "8687", "8666",
				"8787", "6787", "8768", "7778", "7667", "6887", "6686", "6776", "8877", "6868", "6666", "8778", "8787",
				"8777", "6868", "6677", "6877", "8688", "6778", "6878", "8887", "6687", "8666", "7866", "6776", "8866",
				"7778", "6676", "8788", "6867", "8688", "7768", "6866", "8786", "8778", "8676", "7886", "8676", "8688",
				"6766", "7867", "8786", "6766", "6766", "7778", "6887", "6666", "6786", "8676", "7888", "6877", "7876",
				"7886", "6677", "6888", "6776", "8777", "8778", "7876", "6867", "7876", "7887", "6867", "7777", "6778",
				"7766", "6888", "7677", "7678", "7778", "6677", "8766", "8777", "7866", "7777", "8888", "6868", "8886",
				"6676", "8786", "7687", "8787", "7868", "8688", "6666", "8687", "8767", "8777", "8777", "6786", "8888",
				"8688", "8687", "7886", "6886", "8676", "8786", "7687", "7667", "7688", "8678", "7787", "7876", "7878",
				"6666", "6866", "7787", "7866", "6768", "6778", "8787", "8678", "7868", "6786", "8886", "8786", "8688",
				"7776", "8676", "6888", "7767", "8766", "8788", "8676", "8888", "6686", "8667", "6688", "6876", "6667",
				"7688", "8887", "6768", "6778", "8676", "7867", "6776", "7866", "8686", "7668", "7776", "6768", "6767",
				"8666", "6887", "8887", "8888", "8767", "8687", "6787", "8876", "6667", "8686", "6786", "6777", "7766",
				"8878", "8676", "8676", "7777", "6677", "7686", "7887", "7868", "8666", "8778", "8667", "7787", "7678",
				"8766", "7686", "8787", "6886", "8778", "7868", "6778", "8687", "8768", "8666", "8688", "6866", "7788",
				"6777", "7878", "7666", "8878", "7667", "8676", "6778", "6777", "7787", "8866", "8777", "7678", "8767",
				"6666", "6887", "6888", "8666", "6686", "6668", "6687", "8866", "7686", "7678", "8687", "8788", "6767",
				"7877", "6668", "7777", "7878", "8786", "8666", "8866", "7687", "6878", "6878", "7887", "8778", "6867",
				"7688", "8867", "6778", "8778", "7887", "8787", "8786", "8666", "7786", "8777", "6667", "7788", "6886",
				"6766", "8877", "6867", "7767", "6888", "8886", "6888", "8668", "6867", "6768", "8677", "8677", "7676",
				"8666", "7688", "6666", "8668", "8886", "8877", "7768", "7767", "6876", "7776", "7768", "8677", "8688",
				"7668", "7778", "7867", "6668", "8666", "8866", "6867", "7777", "6886", "8676", "6776", "7867", "8686",
				"8878", "7768", "7666", "7788", "7888", "7768", "7886", "6688", "7867", "8788", "7688", "6878", "6886",
				"7676", "7867", "7878", "6778", "6877", "8778", "6686", "6666", "6787", "7766", "7667", "7667", "8778",
				"7776", "6876", "8688", "8666", "7887", "7866", "8866", "7678", "7767", "6777", "6767", "7866", "7667",
				"6867", "8776", "7777", "6788", "6888", "8876", "8866", "6767", "6886", "6868", "7786", "7768", "8667",
				"7687", "6878", "8867", "8767", "6786", "8787", "7687", "8887", "6787", "8668", "8878", "7876", "6688",
				"8868", "8787", "7676", "8686", "6667", "6766", "7776", "7767", "8876", "6668", "8688", "7868", "7867",
				"7666", "8768", "8877", "7777", "7768", "8788", "7876", "8766", "6676", "8668", "6688", "8866", "7688",
				"6768", "8787", "6866", "7666", "7868", "6778", "6868", "6667", "7666", "8768", "7867", "8687", "8768",
				"7667", "6677", "7678", "7876", "7678", "8878", "7667", "6786", "8867", "6766", "6788", "7888", "7677",
				"7887", "6666", "6887", "7886", "7786", "7687", "6677", "6867", "8677", "6676", "6666", "8787", "8676",
				"8787", "8888", "8678", "6767", "7888", "8887", "7688", "8876" };

		String target = "6678";
		System.out.println(new OpentheLock().openLock(deadends, target));
	}

}
